/**
 * 
 */
package com.vinfai.datastructures.tree;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 二叉树顺序存储;
 * 顺序存储主要针对完全二叉树，根据数组下标表示节点之间的逻辑关系。
 * 对一般二叉树容易造成空间浪费。
 * @author vinfai
 *
 */
public class ArrayBinaryTree<T> {
	/**
	 * 二叉树深度
	 */
	private int deep;
	/**
	 * 存储空间;size = 2^deep-1(满二叉树)
	 */
	private Object[] datas; 
	
	private int arraySize ;
	
	public ArrayBinaryTree(int deep,T root){
		if(deep<=0)throw new RuntimeException("deep can't be negative or zero");
		this.deep = deep;
		this.arraySize = (int)(Math.pow(2, deep)-1);
//		datas = Array.newInstance(T., arraySize);
		datas = new Object[arraySize];
		datas[0] = root;
	}
	/**
	 * 增加指定位置index的子节点，数据为data;
	 * 如果index位置无数据(节点为空)，则Exception
	 * @param index index 从0开始
	 * @param data
	 * @param isLeft
	 * @return
	 */
	public boolean addNode(int index,T data,boolean isLeft){
		//从0开始,故2*index+2右节点
		if(2*(index+1)+1>arraySize||datas[index]==null){
			throw new RuntimeException("array index error.");
		}
		if(isLeft){
			datas[2*index+1] = data;
		}else{
			datas[2*index+2] = data;
		}
		return true;
	}
	public T getRoot(){
		return (T)datas[0];
	}
	
	public T getParent(int index){
		if(index<=0||index>=arraySize)
			throw new RuntimeException("index > 2*size+1");
		return (T)datas[(index-1)/2];
		//2*i+1 --> i;
		//2*i --> i;
	}//根据父节点查找子节点
	
	
	/**
	 * 查找左节点
	 * @param index index 表示数组下标
	 * @return
	 */
	public T getLefeNode(int index){
		if(2*index+1>=arraySize){
			throw new RuntimeException("当前节点为叶子节点");
		}
		return (T)datas[2*(index+1)-1];
	}
	
	public T getRightNode(int index){
		if(2*(index+1)>=arraySize){
			throw new RuntimeException("当前节点为叶子节点");
		}
		return (T)datas[2*(index+1)];
	}
	
	public String toString(){
		return Arrays.toString(this.datas);
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		ArrayBinaryTree tree = new ArrayBinaryTree<String>(3, "ROOT");
		
		tree.addNode(0, "1_left", true);
		tree.addNode(0, "1_right", false);
		tree.addNode(1, "2_left", true);
		tree.addNode(1, "2_right", false);
		tree.addNode(2, "3_rigth", false);
		tree.addNode(2, "3_left", true);
		System.out.println(tree.toString());
		int index =2 ;
		String node = (String)tree.getLefeNode(index);
		String node2  = (String)tree.getRightNode(index);
		System.out.println("index "+index+" 的左节点:"+node+" ; 右节点:"+node2);
		
		String parent = (String)tree.getParent(6);
		System.out.println("index "+index+" 的父节点为:"+parent);
	}

}

